The present invention relates to computation in a finite field, and more particularly, to a method and apparatus for obtaining the reciprocal of an arbitrary element in the Galios field GF(2.sup.n).
Computation in the finite field GF(2.sup.n) is employed to the systems each performing the functions related to error correction codes, switching theory and cryptography. Therefore, simplification of the computation in the finite field GF(2.sup.n) plays an important role in enhancing the efficiency of a system performing the functions described above.
To explain conventional computation in the finite field GF(2.sup.n) in detail, we should consider the decoding algorithm for Bose Chaudhuri Hocquenghem (BCH) codes and the computation in the finite field GF(2.sup.n) related to its algorithm.
The decoding algorithm for BCH codes is constituted by the following four steps.
First step: producing syndromes in accordance with the received vector. PA1 Second step: producing the coefficients of an error location polynomial using the syndromes. PA1 Third step: obtaining the roots of the error location polynomial. PA1 Fourth step: producing the error values and then error-correcting based on the error values and the error locations that are the roots of the error location polynomial. PA1 comparing the arbitrary element with the identity element of multiplying; PA1 producing the identity element of multiplying as the reciprocal of the arbitrary element, provided that the arbitrary element is the same as said identity element; PA1 recursively multiplying the identity element by the primitive element so as to produce a first element, and recursively multiplying the identity element by the reciprocal of said primitive element so as to produce a second element, until one of the elements equals the arbitrary element, provided that the arbitrary element is different from the identity element; and PA1 producing the second element as the reciprocal of the arbitrary element if the first element equals the arbitrary element, and producing the first element as the reciprocal of the arbitrary element if the second element equals the arbitrary element. PA1 first means for generating the identity element; PA1 second means for loading the identity element as an initial value and then recursively multiplying it by the primitive element, to produce a first element; PA1 third means for loading the identity element as an initial value and then recursively by multiplying the reciprocal of the primitive element, to produce a second element; and PA1 fourth means for producing the second element as the reciprocal of the arbitrary element when the first element equals the arbitrary element and producing the first element as the reciprocal of the arbitrary element when the second element equals the arbitrary element.
Here, if the BCH codes is for correcting two errors or more, the computation for the reciprocal of the syndrome produced in the first step is performed in the second step. Here, the error location polynomial for the BCH codes which is capable of correcting two errors is represented as: ##EQU1## To obtain .sigma..sub.2, S.sub.1.sup.-1 should be calculated. In the conventional method for computing the reciprocal of an arbitrary element in the finite field, however, no algorithm has yet been proposed which is suitable for hardware implementation.
Accordingly, the computation for obtaining the reciprocal of an arbitrary element in the finite field GF(2.sup.n), utilizes a look-up table which stores in advance the reciprocals of all numbers in the finite field GF(2.sup.n). FIG. 1 shows a look-up table constituted by a read only memory (ROM), in which an arbitrary element or equivalent is applied to the input of the look-up table as an address, to thus produce its reciprocal. Here, the reciprocal stored in the look-up table, as well as the address, are both constituted by n-bits. Therefore, the size of the look-up table is 2.sup.n .times.n.
As described above, in using the look-up table for obtaining the reciprocal, as the number of bits of an element in the finite field GF(2.sup.n) increases, the required memory size increases by a geometric progression.